package com.fr.lintcode;

import java.util.ArrayList;

/**
*作者：furong
*日期：2017年3月7日
*时间：上午11:12:49
*/
public class Q206 {
    class Interval {
        int start, end;

        Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    class LineTree extends Interval {
        public LineTree(int start, int end) {
            super(start, end);
        }

        long sum;
        LineTree left, right;

    }

    /**
     *@param A, queries: Given an integer array and an query list
     *@return: The result list
     */
    public ArrayList<Long> intervalSum(int[] A, ArrayList<Interval> queries) {
        int length = A.length;
        LineTree root = build(0, length - 1);
        calculate(root, A);
        ArrayList<Long> rs = new ArrayList<>();
        for (Interval i : queries) {
            rs.add(query(root, i.start, i.end));
        }
        return rs;
    }

    private LineTree build(int start, int end) {
        LineTree node = new LineTree(start, end);
        if (start < end) {
            int mid = (start + end) / 2;
            node.left = build(start, mid);
            node.right = build(mid + 1, end);
        }
        return node;
    }

    private long calculate(LineTree node, int[] a) {
        if (node == null) {
            return 0;
        } else if (node.start == node.end) {
            node.sum = a[node.start];
            return node.sum;
        }
        long left = calculate(node.left, a);
        long right = calculate(node.right, a);
        node.sum = left + right;
        return node.sum;
    }

    private long query(LineTree node, int start, int end) {
        if (node == null) {
            return 0;
        }
        if (node.start == start && node.end == end) {
            return node.sum;
        }
        int mid = (node.start + node.end) / 2;
        if (mid < start) {
            return query(node.right, start, end);
        } else if (mid >= end) {
            return query(node.left, start, end);
        }
        long left = query(node.left, start, mid);
        long right = query(node.right, mid + 1, end);
        return left + right;
    }
}
